import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 17:21
 * @description 将问题抽象为完全背包问题，一个数可以选择无限次，即求组成和为n的最小个数。
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    int INF = -1;
    public int numSquares(int n) {
        // 预处理出所有可能用到的「完全平方数」
        List<Integer> list = new ArrayList<>();
        int idx = 1;
        while (idx * idx <= n) {
            list.add(idx * idx);
            idx++;
        }

        // f[j] 代表考虑到当前物品为止，凑出 j 所使用到的最小元素个数
        int len = list.size();
        int[] f = new int[n + 1];

        // 处理第一个数的情况
        for (int j = 0; j <= n; j++) {
            int t = list.get(0);
            int k = j / t;
            // 只有容量为第一个数的整数倍的才能凑出
            if (k * t == j) {
                f[j] = k;
            } else { // 其余则为无效值
                f[j] = INF;
            }
        }

        // 处理剩余数的情况
        for (int i = 1; i < len; i++) {
            int t = list.get(i);
            for (int j = t; j <= n; j++) {
                // 当不更新 f[j] 的时候，对应了二维表示中的 f[i - 1][j]

                // 可以更新 f[j] 的前提是：剩余的 j - k * t 也能够被凑出
                // 更新 f[j] 所依赖的 f[j - t] 对应了二维表示中的 f[i - 1][j - k * t]
                if (f[j - t] != INF) {
                    f[j] = Math.min(f[j], f[j - t] + 1);
                }
            }
        }

        return f[n];
    }
}
